package leetcode

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
// Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
// Output: [3,9,20,null,null,15,7]
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	root := &TreeNode{Val: preorder[0]}
	interval := 0
	for i, v := range inorder {
		if v == preorder[0] {
			interval = i
			break
		}
	}
	root.Left = buildTree(preorder[1:1+interval], inorder[0:interval])
	root.Right = buildTree(preorder[1+interval:], inorder[interval+1:])
	return root
}

func buildTree2(preorder []int, inorder []int) *TreeNode {
	inmap := make(map[int]int)
	for i, v := range inorder {
		inmap[v] = i
	}
	var dfs func(ll, lr, rl, rr int) *TreeNode
	dfs = func(ll, lr, rl, rr int) *TreeNode {
		if ll > lr {
			return nil
		}
		v := preorder[ll]
		internal := inmap[v]
		root := &TreeNode{Val: v}
		root.Left = dfs(ll+1, ll+internal-rl, rl, internal-1)
		root.Right = dfs(ll+internal-rl+1, lr, internal+1, rr)
		return root
	}
	return dfs(0, len(preorder)-1, 0, len(inorder)-1)
}
